package main

import (
	"fmt"
)

type CatNode struct {
	no int
	name string
	next *CatNode
}

func InsertCatNode(head *CatNode, newCatNode *CatNode) {

	// 判断是不是第一只猫
	if head.next == nil {
		head.no = newCatNode.no
		head.name = newCatNode.name
		head.next = head // 构成一个环形
		fmt.Println(newCatNode, "加入到环形链表")
		return
	}

	// 先定义一个临时的变量，帮助我们找到环形最后的节点
	temp := head
	for {
		if temp.next == head {
			break
		}
		temp = temp.next
	}
	// 加入到链表中
	temp.next = newCatNode
	newCatNode.next = head

}

// 输出环形链表
func ListCircleLink(head *CatNode) {
	temp := head
	if temp.next == nil {
		fmt.Println("这是空链表")
		return
	}
	fmt.Print("猫的信息为： ")
	for {
		fmt.Printf("[no=%d name=%s] -> ", temp.no, temp.name )
		if temp.next == head {
			break
		}
		temp = temp.next
	}
	fmt.Println()
}

// 删除一只猫
func DelCatNode(head *CatNode, no int) *CatNode {
	
	temp := head
	helper := head
	if temp.next == nil {
		fmt.Println("这是一个空环形链表，无法删除")
		return head
	}
	
	// 如果只有一个节点
	if temp.next == head { 
		temp.next = nil
		return head
	}

	// 将helper定位到链表最后
	for {
		if helper.next == head {
			break
		}
		helper = helper.next
	}

	// 如果包含两个以上的节点
	flag := true
	for {
		if temp.next == head { // 说明已经比较到最后一个，最后一个还没比较
			break
		}
		if temp.no == no {

			if temp == head { // 说明删除的是头节点
				head = head.next
			}

			// 找到了
			helper.next = temp.next
			fmt.Printf("去掉了第%d个的猫猫\n", no)
			flag = false
		}
		temp = temp.next // 移动，比较
		helper = helper.next // 移动，一旦找到要删除的节点，helper
	}
	// 这里还要比较一次，如果flag为真，则for循环没有删除
	if flag {
		if temp.no == no {
			helper.next = temp.next
			fmt.Printf("去掉了第%d个的猫猫\n", no)
		} else {
			fmt.Println("没有这只猫")
		}
	}
	return head
}

func main() {

	// 这里初始化环形链表的头节点
	head := &CatNode{}

	// 创建一只猫
	cat1 := &CatNode {
		no : 1,
		name : "tom",
	}

	cat2 := &CatNode {
		no : 2,
		name : "tom",
	}

	cat3 := &CatNode {
		no : 3,
		name : "tom",
	}

	InsertCatNode(head, cat1)
	InsertCatNode(head, cat2)
	InsertCatNode(head, cat3)
	head = DelCatNode(head, 3)
	ListCircleLink(head)

}